Сайт Информационных Технологий

СПОСОБ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ЭВРИСТИЧЕСКОГО МЕТОДА ОПТИМИЗАЦИИ В УСЛОВИЯХ ОБЪЕКТНО-ОРИЕНТИРОВАННЫХ СИСТЕМ

А.О. Глухов

Полоцкий государственный университет

Abstract — With the recent advances in the communication technology and availability of powerful desktop computers, networking and multiprocessing has gained popularity for application development. This paper describes a framework for development of object-distributed optimization algorithms. It is a special class of heuristic algorithms, which can be defined as the set of synchronized object-processes. Using of this class algorithms open possibility of incr ease the efficient of optimal result searching by heuristic method. The source of such efficient increasing we find in parallel computing and objects communication during the searching.

Современные вычислительные системы строятся с учетом таких возможностей повышения их эффективности, как распределенность структуры, использование коммуникационных механизмов сетевых с ред, многопроцессорная обработка. Результатом развития технологий разработки программных систем на сегодня является целый ряд стандартов, которые регламентируют их архитектуру, средства управления процессами, механизмы взаимодействия систем, и т.д.. Межд ународные стандарты разработаны ANSI, ISO, IEC, IEEE и другими организациями. В рамках этих стандартов уже прочно закрепилось применение объектно-ориентированной технологии при разработке программных систем. Это говорит о том, что объектная концепция пре дставления действительности более универсальна по сравнению с ранее используемыми и имеет ряд преимуществ, благодаря которым она успешно используется при разработке и моделировании сложных систем.

В объектно-ориентированной концепции понятие сущности интерпретируется исходя из двух аспектов. С одной стороны - это структура данных, с другой - это программный код, определенная совокупность методов, соответственно выделяют структур ный и поведенческий аспекты понятия сущности. Именно это коренное отличие объектно-ориентированного подхода к анализу и программированию от других методов позволяет говорить об объектно-распределенных процессах, так как каждый объект становится активной единицей, обладающей своей собственной памятью и своим поведением.

Существующее программное обеспечение, которое традиционно используется для решения разнообразных задач оптимизации, имеющих место в распределенных объектно-ориентированных системах, н е учитывает особенности функционирования объектных систем, такие как: а) активный характер объектов; б) возможность распараллеливания вычислений в рам ках обработки событий объектами; в) взаимодействие между объектами; основанное на обмене сообщениями; г) динамическое связывание объектов; д) существование отношений структуризации среди объектов в объектно-ориентированных системах и др.

Распределенная оптимизация развивалась довольно интенсивно применительно к распределенным СУБД. На сегодняшний день существует множество подходов к решению задач оптимизации выполнения запросов в распределенных реляционных базах данных . В этой области существует огромное количество публикаций как зарубежных, так и отечественных ученых. Однако не только СУБД столкнулись с этой проблемой - практически любые сложные распределенные системы решают задачу оптимального управления. Поэтому оч ень важно рассмотреть специфику и подходы к решению данной задачи применительно к объектным системам и средам.

Основная идея состоит в возможности повышения эффективности эвристического метода оптимизации за счет превращения объектов в активные элементы поиска оптимального решения. Тогда уже речь идет не об одном поисковом процессе, основанном на том или ином принципе, а о множестве взаимосвязанных поисковых процессов.

В данной работе вводится новое понятие – объектно-распределенный алгоритм, как обозначение определенного принципа организации поиска решения. Дадим его определение:

Объектно-распределенным поиском (алгоритмом) будем считать эвристический поиск, носящий локальный относительно объектов характер и имеющий вид множества активных синхронизированных процессов объектов, основной задачей которых является поиск варианта решения на основе оценки ситуации в пределах межобъектных связей и сравнение его с вариантами соседних объектов для выбора наилучшего.

С одной стороны может показаться, что изменение задачи требует непомерных усилий на перепрограммирование активностей объектов, однако, использование таких особенностей объектно-ориентированного подхода, как наследование и полиморфизм, позволяет легко вводить любые согласованные изменения в поведение объектов, а, следовательно, и в задачу.

Автор считает, что организация поиска по объектно-распределенному принципу дает значительное повышение эффективности эвристического метода, не только связанного с возможностью распараллеливания вычислений, но и при работе на одном проц ессоре. В качестве резерва повышения эффективности рассматривается конкурирующий характер поиска, когда объекты как бы соревнуются в поиске решения. Каждый объект осуществляет поиск на основании информации, доступной в пределах его межобъектных связей. З атем обменивается своим решением с соседями, сравнивая его с решениями соседей. Сравнение должно предусматривать выполнение некоторых адаптирующих процедур по отнесению того или иного варианта к условиям конкретного объекта. Выбирается только наилучший в ариант. По сути идет одновременный поиск по всем объектам.

Объектно-распределенные алгоритмы позволяют использовать все вышерассмотренные резервы повышения эффективности поиска в полной мере. То есть сохраняют и даже повышают свою эффективны в условиях распределенных вычислительных систем.

В основу формализма описания объектной системы была положена базовая концепция объектно-ориентированного программирования, которая взята из материалов Европейских конференций по ООП.

Базовая концепция включает в себя такие понятия, как:

  1. T={d1,d2,…,dn} – множество типов данных; y=y(i,d) – атрибут объекта, i=1..n, dI di; yob={y1,y2,…,yk} – множество атрибутов объекта;
  2. X={x1,x2,…,xm} – алфавит событий;
  3. XobI X, Xob=BobE DobE UobE Cob – интерфейс, Bob – конструкторы, Dob – деструкторы, Uob, Cob – события модификации и связи;
  4. sI 2Xob – сценарий;
  5. L = {sj | " sjI L, " skI L, k? j: sk? sj} – жизненный цикл; Lob – множество жизненных циклов объекта;
  6. PobI Lob – процесс;
  7. Mob=(Vob,Pob) – объектная модель, Vob – наблюдаемая структура, Pob – процесс;
  8. o=(Xob,Yob,i,Mob,L) – объект, Xob – интерфейс, Yob – множество атрибутов, i – идентификатор, Mob – объектная модель, L – жизненный цикл;
  9. c=c(Mob) – класс объектов;
  10. M1® M2: Y1I Y2, X1I X2 – наследование;
  11. S=(T,X,I,C,O) – объектная система, T – множество типов данных , X – алфавит событий, I – множество идентификаторов объектов, C – множество классов (объектных моделей), O – множество существующих объектов.

В материалах конференций также достаточно подробно рассматриваются разнообразные отношения наследования, такие как агрегирование, инстанцирование, множественное наследование.

В развитие данного формализма было предложено разделить множество событий модификаций на два непересекающихся множества событий связи и событий модификации. Соответственно такому делению вводятся понятия сценария связи и сценария модиф икации. Формализуется понятие состояние и переход уже в этом новом контексте. Влияние событий связи и модификации на поведение объекта различно. Данное различие мы фиксируем в области определения операторов связи и модификации. Данные операторы являются формальным определением влияния событий на поведение объекта. Множества операторов связи и модификации соответствует определенной объектной модели и, поэтому, является статическим. Совокупность операторов связи и модификации, имеющих место в объектной си стеме, мы обозначили как "статическая стратегия". При оптимизации некоторого критерия в объектной системе, объект выполняет сценарий вида: связь® модификация® … связь® модификация® ... Окончание выполнения данного сценария зависит от сходимости системы операторов связи и модификации. Данный процесс мы определили как "статическое регулирование". Запишем вышесказанное формально:

  1. sCob={sI 2Xob | $ cI Cob: cI s, " eI s: eI Uob}, sUob={sI 2Xob | $ uI Uob: uI s, " eI s: eI Cob} – сценарии связи и модификации; Xob – объектный интерфейс; s – сценарий; c, u, e – события; Cob, Uob – множества событий связи и модификации;
  2. y=f(Y,s) – функция перехода; Y – состояние; s – сценарий перехода; y – состояние объекта;
  3. F: {yi=fij(Y,sij) | sijI 2X, sijI SDobi} – множество функций перехода; SDobi – множество сценариев уничтожения i-го объекта;
  4. (Y,F) – информационный базис;
  5. Y=YCE YI – первичные и вторичные переменные;
  6. J : {yIi=j ij(YC)} – множество операторов связи; yIiI YI, yIiI yi – вторичные переменные объекта oi; OC(oi)={oj | " oj: $ yjkI yj, $ j ikI J : j ik/ yik? 0} – множество объектов, связанных с объектом oi;
  7. M : {yi=m ij(y/i)} – множество операторов модификации; yi, y/i – старое и новое состояния объекта oi;
  8. Y =(J ,M ) – статическая стратегия – сходящаяся система операторов связи и модификации.

Постановка обобщенной задачи объектно-распределенной оптимизации звучит следующим образом:

Имеется объектно-ориентированная система S, в которой необходимо минимизировать некоторый критерий C(Y), где Y – множество переменных системы, в системе определено также множество булевых функций ограничений H(Y). Требуется найти оптимальную статическую стратегию, при которой в результате статического регулирования объектная система придет к своему оптимальному состоянию.

Y *=(J *,M *): C(Y)® min, H(Y)=true

Решение данной задачи предлагается искать в виде множества эвристических правил оптимизации, сформулированных для пространства отдельно взятого объекта.

Y *=(J *=W CI W ,M *=W UI W ), где

W : yj=w i(d j) | " p iI P *, ojI O: d jI D i – алгоритм решения;

W =W CE W U – множество преобразований под действием правил;

P ={p 1,p 2,…,p n} – множество правил оптимизации;

p =p (D ,w ) – правило;

D ={d 1,d 2,…,d m} – множество ситуаций;

w =w (d ) – действие правила;

Практически более значимым алгоритмом решения поставленной задачи является тот вариант предложенного общего алгоритма, для которого:

p i=p i(d (o),w i) – правила, определенные для локальной ситуации абстрактного объекта o.

Для предложенного типа алгоритмов характерно:

  1. Возможность распараллеливания поиска по объектам и кластеризация системы объектов для переноса ее в распределенную среду;
  2. Обмен поисковой информацией в пределах межобъектных связей в процессе поиска;
  3. Конкурирующий локальный характер поиска решения объектом.

Оптимизирующая объектная модель строилась на основании объектно-ориентированного анализа процесса оптимизации. При рассмотрении процесса оптимизации был выделен класс "статический оптимизатор" как абстракция поведения объекта. Данный к ласс является абстрактным.

Сценарий поведения статического оптимизатора иллюстрирует диаграмма состояний и переходов (см. Рис.1).

Рис.1. Диаграмма состояний и переходов класса “стати ческий оптимизатор”

В качестве примера рассматриваются следующие задачи: задача управления транспортными потоками, задача составления расписания, задача календарного планирования, задача коммивояжера и з адача о наилучшем размещении. Оптимизирующие объектные модели конкретизируются в соответствии с прагматикой решаемой задачи.

Для исследования вычислительной сложности алгоритмов была построена итерационная модель системы. Первый вариант алгоритма решения задачи коммивояжера представлял собой поиск из одного узла, а второй - поиск из всех узлов. Среднее откло нение решения от оптимального в первом варианте алгоритма составило 7.6%; для второго варианта – 1.3%. Оценивая сложность, можно сказать, что число итераций не превосходит значения 2n для первого варианта и, соответственно, 2n2

- для второго, где n - количество узлов транспортной сети (см. Рис.2). Это достаточно хорошие результаты для приближенных алгоритмов и они были подтверждены при экспериментировании с сетями из 30, 100 и 200 узлов.

Рис.2. Зависимость числа итераций поиска от количества узлов

При исследовании эффективности объектно-распределенных алгоритмов в зависимости от способа реализации параллельности были получены следующие результаты. По способу синхронизации предп очтительнее простая синхронизация, односторонняя при небольшом числе отказов и асинхронная. Синхронная - применима лишь при малом ожидании обработки сообщения и малом числе отказов.

Литература

  1. Donald Lewine POSIX Programmer’s Guide – USA, Sebastopol: O’Reilly & Associates, Inc., 1991. – 640 p.
  2. John Bloomer Power Programming with RPC. – USA, Sebastopol: O’Reilly & Associates, Inc., - 1992. – 486 p.
  3. John Shirley, Wei Hu & David Magid Guide to Writing DCE Applications – USA, Sebastopol: O’Reilly & Associates, Inc., 1994. – 462 p.
  4. ECOOP’92: European conference on OOP. - Berlin etc.: Springer, 1992. – 426p.
Site of Information Technologies
Designed by  inftech@webservis.ru.